package 算法.位运算;

import java.util.ArrayList;
import java.util.HashMap;

public class JZ56数组中只出现一次的两个数字 {
    //异或运算
    /**
     * 只有一个出现一次，其他出现两次 ， 则进行全员异或即可
     *
     * 这里有两个只出现一次的数字：
     *  1. z = x ^ y
     *  2. 求 第一个x 与 y 不相等的位
     */
    public int[] FindNumsAppearOnce (int[] array) {
        int res1 = 0;
        int res2 = 0;
        int temp = 0;
        //遍历数组得到 a^b  其他相同的已经消除了 同0异1
        for(int i = 0; i < array.length; i++)
            temp ^= array[i];

//        int k = 1;
//        //找到两个数不相同的第一位
//        while((k & temp) == 0)
//            k <<= 1;
        //如果一个数与自身的负数相与可以得到最低位的1的位置的数，然后其余位补0。
        //比如1001010，与自身负数相与后的结果是0000010；
        temp &= -temp;
        int k = temp;
        //把 x 与 y 放进两个子数组中
        for(int i = 0; i < array.length; i++){
            //遍历数组，对每个数分类
            //因为这两个数字肯定不同所以得到的结果中在二进制表示中至少有一位是1，我们在结果中找到第一个为1的位置，记为n，根据第n位是否为1将数组分成两部分。
            if((k & array[i]) == 0)
                res1 ^= array[i];
            else
                res2 ^= array[i];
        }
        //整理次序
        if(res1 < res2)
            return new int[] {res1, res2};
        else
            return new int[] {res2, res1};
    }


    //哈希表
    public int[] FindNumsAppearOnce2 (int[] array) {
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
        ArrayList<Integer> res = new ArrayList<Integer>();

        //遍历数组
        for(int i = 0; i < array.length; i++)
            //统计每个数出现的频率
            if(!mp.containsKey(array[i]))
                mp.put(array[i], 1);
            else
                mp.put(array[i], mp.get(array[i]) + 1);

        //再次遍历数组
        for(int i = 0; i < array.length; i++)
            //找到频率为1的两个数
            if(mp.get(array[i]) == 1)
                res.add(array[i]);
        //整理次序
        if(res.get(0) < res.get(1))
            return new int[] {res.get(0), res.get(1)};
        else
            return new int[] {res.get(1), res.get(0)};
    }
}
